翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

addition chain : ウィキペディア英語版
addition chain
In mathematics, an addition chain for computing a positive integer ''n'' can be given by a sequence of natural numbers ''v'' and a sequence of index pairs ''w'' such that each term in ''v'' is the sum of two previous terms, the indices of those terms being specified by ''w'':
: ''v'' =(''v''0,...,''v''''s''), with ''v''0 = 1 and ''v''''s'' = ''n''
:for each 0< ''i'' ≤ ''s'' holds: ''v''''i'' = ''v''''j'' + ''v''''k'', with ''w''''i''=(''j,k'') and 0 ≤ ''j,k'' ≤ ''i'' − 1
Often only ''v'' is given since it is easy to extract ''w'' from ''v'', but sometimes ''w'' is not uniquely reconstructible. An introduction is given by Knuth.〔D. E. Knuth, ''The Art of Computer Programming'', Vol 2, "Seminumerical Algorithms", Section 4.6.3, 3rd edition, 1997〕
==Examples==
As an example: ''v'' = (1,2,3,6,12,24,30,31) is an addition chain for 31 of length 7, since
:2 = 1 + 1
:3 = 2 + 1
:6 = 3 + 3
:12 = 6 + 6
:24 = 12 + 12
:30 = 24 + 6
:31 = 30 + 1
Addition chains can be used for addition-chain exponentiation: so for example we only need 7 multiplications to calculate 531:
:52 = 51 × 51
:53 = 52 × 51
:56 = 53 × 53
:512 = 56 × 56
:524 = 512 × 512
:530 = 524 × 56
:531 = 530 × 51

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「addition chain」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.